import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Stack;


//String Construction from Read-Pairs Problem
public class Ex5_4 {


	public Ex5_4() {}

	public static void main(String[] args) {
		Ex5_4 exer = new Ex5_4();
		Integer m = 300;
		ArrayList<Pair> pairs = exer.getPairs(
				"C:\\Users\\josemfer\\Downloads\\dataset_58_14.txt");
		HashMap<Pair,ArrayList<Pair>> graph = exer.getGraph(pairs);
		ArrayList<Pair> path = exer.getEulerPath(graph);
		exer.printPath(path, m);

	}

	
	
	private void writeFile(String text) {
		Writer writer = null;

		try {
		    writer = new BufferedWriter(new OutputStreamWriter(
		          new FileOutputStream("C:\\Users\\josemfer\\Downloads\\ex5_4_out.txt"), "utf-8"));
		    writer.write(text);
		} catch (IOException ex) {
		  // report
		} finally {
		   try {writer.close();} catch (Exception ex) {}
		}
	}
	
	
	private void printPath(ArrayList<Pair> path, Integer m) {
		String keys = "";
		String values = "";
		for (Pair pair : path) {
			String key = pair.key();
			String value = pair.value();
			keys += key.substring(0,1);
			values += value.substring(value.length()-1,value.length());			
		}
		Integer k = path.get(0).key().length();
		String text = keys + values.substring(  values.length() - 2*k - m,values.length());
		writeFile(text);
	}


	private Pair selectStartNode(HashMap<Pair,ArrayList<Pair>> reads) {
		HashMap<Pair,Integer> inDegrees = new HashMap<Pair,Integer>();
		for (Entry<Pair,ArrayList<Pair>> read : reads.entrySet()) {			
			ArrayList<Pair> outgoings = (ArrayList<Pair>) read.getValue();
			for (Pair outgoing : outgoings) {
				if (inDegrees.containsKey(outgoing)) {
					Integer actualDegree = inDegrees.get(outgoing);
					inDegrees.put(outgoing, actualDegree + 1);					
				} else {
					inDegrees.put(outgoing, 1);		
				}
			}
		}

		for (Entry<Pair,ArrayList<Pair>> read : reads.entrySet()) {			
			Pair origin = read.getKey();
			ArrayList<Pair> outgoings = read.getValue();
			Integer inDegree = inDegrees.get(origin);
			if (inDegree == null) {
				inDegree = 0;
			}
			Integer outDegree = outgoings.size();
			if (outDegree == inDegree + 1) {
				return origin;
			}			
		}	

		return null;
	}

	private ArrayList<Pair> getEulerPath(HashMap<Pair,ArrayList<Pair>> aGraph) {
		ArrayList<Pair> eulerPath = new ArrayList<Pair>();
		Stack<Pair> stack = new Stack<Pair>();
		HashMap<Pair,ArrayList<Pair>> graph = 
				new HashMap<Pair,ArrayList<Pair>>(aGraph);
		Pair current = selectStartNode(graph);
		ArrayList<Pair> outgoings = graph.get(current);

		do {								
			//remove the last vertex from the stack and set it as the current one
			if (outgoings == null || outgoings.size() == 0) {			
				eulerPath.add(current);
				current = stack.pop();
			} else { 
				// add the vertex to the stack
				stack.push(current);
				//take any of its neighbors
				Pair outgoing = outgoings.get(0);
				// remove the edge between that vertex and selected neighbor
				if (outgoings.size() == 1) {
					graph.remove(current);
				} else {
					outgoings.remove(0);
				}
				//set that neighbor as the current vertex
				current = outgoing;			
			}	
			outgoings = graph.get(current);			
		} while(!stack.isEmpty() ||  outgoings != null);

		eulerPath.add(current);
		Collections.reverse(eulerPath);
		return eulerPath;		
	}


	private HashMap<Pair,ArrayList<Pair>> getGraph(ArrayList<Pair> pairs) {
		HashMap<Pair,ArrayList<Pair>> graph = 
				new HashMap<Pair,ArrayList<Pair>>();
		for (Pair pair : pairs) {
			Pair prefix = new Pair( 
					pair.key().substring(0,pair.key().length()-1),
					pair.value().substring(0,pair.value().length()-1));
			Pair sufix = new Pair( 
					pair.key().substring(1,pair.key().length()),
					pair.value().substring(1,pair.value().length()));
			ArrayList<Pair> outgoings = graph.get(prefix);
			if (outgoings == null) {
				outgoings = new ArrayList<Pair>();
				outgoings.add(sufix);
				graph.put(prefix, outgoings);
			} else {
				outgoings.add(sufix);
			}
		}		
		return graph;
	}


	private ArrayList<Pair> getPairs(String file) {		
		ArrayList<Pair> pairs = new ArrayList<Pair>();		
		try {
			BufferedReader br = new BufferedReader(new FileReader(file));
			String line;		
			while ((line = br.readLine()) != null) {
				line = line.trim();
				String[] splitted = line.split("\\|");
				pairs.add(new Pair(splitted[0],splitted[1]));			
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
		return pairs;
	}


}
